package cn.edu.cdu.argorithm.impl;

import cn.edu.cdu.argorithm.IMergeSortedArray;

public class MergeSortedArray {
    public static class Solution1 implements IMergeSortedArray {
        @Override
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int length = m + n, ptr1 = 0, ptr2 = 0, idx = 0;
            int[] arr = new int[length];
            while(ptr1 < m && ptr2 < n) {
                if(ptr1 == m) {
                    arr[idx++] = nums2[ptr2++];
                } else if(ptr2 == n) {
                    arr[idx++] = nums1[ptr1++];
                } else if(nums1[ptr1] <= nums2[ptr2]) {
                    arr[idx++] = nums1[ptr1++];
                } else {
                    arr[idx++] = nums2[ptr2++];
                }
            }
            for(int i = 0; i < length; i++) {
                nums1[i]= arr[i];
            }
        }
    }

    public static class Solution2 implements IMergeSortedArray{
        @Override
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int length = m + n, ptr1 = 0, ptr2 = 0, idx = 0;
            int[] arr = new int[length];
            while(ptr1 < m && ptr2 < n) {
                if(nums1[ptr1] < nums2[ptr2]) {
                    arr[idx++] = nums1[ptr1++];
                } else {
                    arr[idx++] = nums2[ptr2++];
                }
            }
            if(ptr1 == m) {
                System.arraycopy(nums2, ptr2, arr, idx, n - ptr2);
            } else {
                System.arraycopy(nums1, ptr1, arr, idx, m - ptr1);
            }
            System.arraycopy(arr, 0, nums1, 0, length);
        }
    }

    public static class Solution3 implements IMergeSortedArray{
        @Override
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int ptr = m + n - 1, ptr1 = m - 1, ptr2 = n - 1;
            while(ptr1 > -1 || ptr2 > -1) {
                if(ptr1 == -1) {
                    nums1[ptr--] = nums2[ptr2--];
                } else if (ptr2 == -1) {
                    nums1[ptr--] = nums1[ptr1--];
                } else if (nums1[ptr1] < nums2[ptr2]) {
                    nums1[ptr--] = nums2[ptr2--];
                } else {
                    nums1[ptr--] = nums1[ptr1--];
                }
            }
        }
    }
}
